Several cryptographic algorithms can be used in such a manner that some device which is relatively less powerful (computationally speaking), plays the role of a “prover” in relation to another, more powerful, device playing the role of a “verifier”. Such algorithms are of particular interest to deployments that use computationally-weak prover devices such as RFID tags communicating with much more powerful verifier devices such as tag-readers.
As is well-known in the art, one way to reduce computations on a device is—whenever applicable—by the use of cryptographic “coupons”. A coupon comprises, first, a randomly chosen number r and, second, a “reduced-coupon” x such that x=ƒ(r), where ƒ is a one-way function the calculation of which requires intensive computations (such as modular exponentiations). An example of such a cryptographic algorithm is the well-known “Digital Signature Algorithm” DSA (Standard FIPS 186-2 published by the National Institute of Standards and Technology), wherein x=(gr mod p) mod q, where p and q are prime numbers and g is an integer derived from p and q; another example is the “GPS” algorithm, wherein x=gr mod n, where n is a large integer, and g is an integer (typically much) smaller than n (for a detailed description of some variants of GPS, see for example International Standards ISO/IEC 9798-5 and 14888-2).
In their article titled “Public Key Cryptography and RFID Tags”, M. McLoone and M. J. B. Robshaw show indeed, based on a detailed analysis of the GPS algorithm, that public-key cryptography can advantageously be implemented in low-cost RFID tags.
Thus, whenever a computationally-weak prover device enters a cryptographic protocol using such an algorithm, it may use a coupon in order to reduce computations, thereby significantly reducing the duration of the protocol.
Usually, a set of coupons (r,x) is downloaded in the coupon-consuming device during the device fabrication process. Once this set of coupons has been consumed, one may either simply throw away the device if its cost of fabrication is low enough, or else have the coupon-consuming device itself compute a new set of coupons, or else have a computationally-powerful device compute a new set of coupons which are then downloaded in the coupon-consuming device.
However, it must be born in mind that the number of successive protocols in which a coupon-consuming device can enter is limited by the amount of memory required for storing the coupons. It is hence desirable to reduce the amount of memory occupied by each coupon. Such an improvement is actually known: it consists in storing in the coupon-consuming device during the fabrication process a set of reduced-coupons xi=ƒ(ri) (where i is an index for labeling the coupon), but not the corresponding random numbers ri, which are, instead, successively (viz., keeping with successive values of the index i) regenerated in the device whenever needed for entering a cryptographic protocol. This may be achieved for example by having the device calculate ri=PRFK(i), where K is a “regeneration key” owned by the device, and PRF is a keyed pseudo-random function the calculation of which requires only light computations.
In view of the above, it may be surprising to notice that the reloading of a coupon-consuming device with a set of reduced-coupons only, by connecting it to a computationally-powerful reloading device, has never been considered so far.
One reason for this may be that in most practical deployments, the communications environment is insufficiently secured. There exists therefore a danger that a device may inadvertently request reloading from a fake or compromised coupon-reloading device, which will attempt to provide phoney, arbitrarily chosen “reduced-coupons”. Since an attacker does not know the secret key K used in the calculation of the pseudo-random function PRFK, it is unable to calculate the pseudo-random numbers ri=PRFK(i); thus, any such “reduced-coupon” subsequently used by the coupon-consuming device in a cryptographic protocol with a verifier device will be computationally unrelated to the number ri concurrently used. This represents a so-called “denial-of-service” attack, since it essentially disrupts the regular operation of the coupon-consuming device after reloading.